package com.wdc.simple.day04;



public class BinarySearchPlus {


    /**
     * 二分查找
     * @param a 待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引、没找到返回 -1
     */
    public static int binarySearchBasic(int[] a,int target){
        int left = 0;
        int right = a.length - 1;

        while(left <= right){
            int m = (left+right)/2;

            if(a[m] < target){
                left = m +1;
            }else if (a[m] > target) {
                right = m - 1;
            }else {
                return m;
            }
        }

        return -1;
    }

    /**
     * 线性查找
     * @param a 待查找的数组
     * @param target 待查找的目标值
     * @return 找到返回索引、没找到返回 -1
     */

    public static int linearSearch(int[] a,int target){
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target){
                return i;
            }
        }
        return -1;
    }

    /*
        假设 while 的循环次数已经知道为 L次
        对于二分查找基础版，带查找元素在最左边（查找L 次）和最右边的查找次数(2*L 次) 不一样 所以有以下改进
        核心就是让right 指向一定不是带查找的元素
     */
    public static int binarySearchPlus(int[] a,int target){
      int left = 0 , right = a.length;
      while ( 1 <(right - left)){
           int m = (left + right) >>> 1;
           if (target < a[m]){
               right = m;
           }else {
               left = m;
           }
      }

      if (a[left] == target){
          return left;
      }else {
          return -1;
      }
    }

}
